package 蓝桥算法;

import 二叉树.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class day17 {
    public List<Integer> preorderTraversal(TreeNode root){//中序遍历
        List<Integer>result=new ArrayList<>();

        if(root==null){
            return result;
        }
        LinkedList<TreeNode> stack=new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            result.add(node.val);
            if(node.left!=null){
                stack.push(node.left);
            }
            if(node.right!=null) {
                stack.push(node.right);
            }
        }
        return result;
    }
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer>result=new ArrayList<>();
        if(root==null){
            return result;
        }
        LinkedList<TreeNode>stack=new LinkedList<>();
        TreeNode cur=root;
        stack.push(cur);
        while(cur!=null||stack!=null){
            if(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            else{
                cur=stack.pop();//把左侧的弹出，继续看右侧的左孩子
                result.add(cur.val);
                cur=cur.right;//此时可能cur的左侧不为null则进上册循环
            }
        }
        return result;
    }
    public List<Integer> postorderTraversal(TreeNode root){
        List<Integer> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        LinkedList<TreeNode>stack=new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            result.add(node.val);
            if(node.left!=null){
                stack.push(node.left);
            }
            if(node.right!=null){
                stack.push(node.right);//栈不为空依旧进行以下操作
            }
        }
        return result;
    }
}
